This application claims the priority of Korean Patent Application No. 2003-97151, filed on Dec. 26, 2003, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein in its entirety by reference.
1. Field of the Invention
The present invention relates to an apparatus and method for performing packet header lookup based on sequential lookup, and more particularly, to an apparatus and method for performing packet header lookup based on sequential lookup, which is used in a security system such as an intrusion detection system (IDS).
2. Description of the Related Art
A device like a firewall that examines a packet received via a network to protect both network and application attacks, or an intrusion detection system (IDS) examines the combination of a header and a payload of the packet to check whether the packet is abnormal or not. Contrary to the examination of the payload of the packet, in order to examine the header of the packet, each field having a designated location of the header should be examined using various combinations of the header and the payload of the packet. In addition, there is the case where 1-bit is compared with each other in the field of the header. Thus, each bit should be treated as a don't care. In the case of a TCP packet having the size of the header greater than 40 bytes, rules comprised of various combinations of the header and the payload of the packet in data of the header should be compared with one another at the same time.
Meanwhile, the IDS makes various intrusion detection rules using combination obtained from the header of the packet and string information of the payload of the packet. In the case of the intrusion detection rules, there are a plurality of rules comprised of header fields having the same combination and comprised of different strings in the payload. For example, in the case of an Http rule of the intrusion detection rules, several hundreds of rules comprised of a header combination in which the number of a destination port is 80 and comprised of different contents, exist in a TCP protocol. There are several thousands of rules in the IDS. However, there are several hundreds of combinations of header information of the packet in the IDS. Thus, the number of the combinations is not larger than the number of the rules. In addition, these rules should show comparison results of only 1-bit of a specific portion of the header.
In order to solve this complexity, in prior arts, a rule constituting the header is hard-coded using hardware logic. However, there is a limitation on hard-coding when a new rule is added to existing rules. Due to this hardware limitation, in prior arts, only restricted fields of header fields of a packet are searched for using a ternary content addressable memory (TCAM). However, in the case of the TCAM, the TCAM having inputs more than 40 bytes should be operated in only a TCP protocol, and most of fields should be treated as a don't care while rules are combined. On these conditions, many fields are not used in the TCAM, and thus the TCAM is a very ineffective solution. In addition, detection rules for an IP option or a TCP option of the TCP protocol exist in the TCAM. Thus, it is difficult to make various combinations using the TCAM. In addition, power consumption is large and a large physical space is needed.
Furthermore, since information about other fields excluding fields used in lookup is disregarded, correct lookup results cannot be obtained. When all fields of the header are used to perform lookup, in the case of the TCP protocol, lookup should be performed on fields more than 40 bytes at the same time. Thus, so much hardware is needed to constitute an entry. In addition, in general, the number of fields constituting a rule is not large, and thus, so much hardware is needed to constitute an entry. Furthermore, the meaning of fields constituting the header and the size of the header vary according to types of packets. Thus, different lookup entries should be designated in advance in accordance with types of protocols. Furthermore, there is a limitation on the addition of a new rule to existing rules.